package leetcode_1201_1300;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LeeCode_1278 {
    public static void main(String[] args) {
        System.out.println(palindromePartition("abc", 2));
        System.out.println(palindromePartition("aabbc", 3));
    }
    private static int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n][k + 1];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int key = i * n + j;
                map.put(key, charge(s, i, j));
            }
        }
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 1000);
        }
        dp[0][1] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= Math.min(i + 1, k); j++) {
                for (int p = 0; p < i; p++) {
                    if (j == 1)
                        dp[i][j] = charge(s, 0, i);
                    else
                        dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + map.get((p + 1) * n + i));
                }
            }
        }
        return dp[n - 1][k];
    }
    private static int charge(String s, int l, int r){
        int res = 0;
        while (l < r){
            if (s.charAt(l) != s.charAt(r)){
                res++;
            }
            l++;
            r--;
        }
        return res;
    }
}